#include <stdio.h>
#include <iostream>
using namespace std;

struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
//create bsTree
void CreateBSTree(BSTreeNode** inputNode, int value);
//
void ChangeBSTreeToLinkList(BSTreeNode* header, BSTreeNode* ender, BSTreeNode* root);

int main()
{
	BSTreeNode* pRoot = NULL;
	BSTreeNode* header = new BSTreeNode();
	BSTreeNode* ender = new BSTreeNode();
	BSTreeNode* moveHeader = NULL;
	
	CreateBSTree(&pRoot, 10);
	CreateBSTree(&pRoot, 6);
	CreateBSTree(&pRoot, 4);
	CreateBSTree(&pRoot, 8);
    CreateBSTree(&pRoot, 14);
    CreateBSTree(&pRoot, 12);
	CreateBSTree(&pRoot, 16);
	
	ChangeBSTreeToLinkList(header, ender, pRoot);
	
	moveHeader = header;
	
	while(moveHeader != NULL && moveHeader->m_pRight != NULL)
	{
		moveHeader = moveHeader->m_pRight;
		if (moveHeader->m_pRight != NULL)
		{
			cout << moveHeader->m_nValue << endl;
		}
	}
	
	delete header;
	delete ender;
	system("pause");
	return 0;
}

void CreateBSTree(BSTreeNode** inputNode, int value)
{
	if (NULL == *inputNode)
	{
		*inputNode = new BSTreeNode();
		(*inputNode)->m_pLeft = NULL;
		(*inputNode)->m_pRight = NULL;
		(*inputNode)->m_nValue = value;
	}
	else
	{
		if (value < (*inputNode)->m_nValue)
		{
			CreateBSTree(&((*inputNode)->m_pLeft), value);
		}
		else if (value > (*inputNode)->m_nValue)
		{
			CreateBSTree(&((*inputNode)->m_pRight), value);
		}
	}
}

void ChangeBSTreeToLinkList(BSTreeNode* header, BSTreeNode* ender, BSTreeNode* root)
{
	if (root == NULL)
	{
		header = NULL;
		ender = NULL;
		return;
	}

	BSTreeNode* tempRoot = new BSTreeNode();
	*tempRoot = *root;

	header->m_pRight = root;
	ender->m_pLeft = root;
	root->m_pLeft = header;
	root->m_pRight = ender;

	ChangeBSTreeToLinkList(header, root, tempRoot->m_pLeft);
	ChangeBSTreeToLinkList(root, ender, tempRoot->m_pRight);
	delete tempRoot;
}